[doc] Les files : type abstrait

Lien Moodle : https://moodle.epita.fr/mod/page/view.php?id=108769

Contenu du cours

Les files : le type abstrait

3 opérations :

• premier : pour connaître la valeur du premier ;
• enfiler : pour ajouter un nouvel élément ;
• défiler : pour supprimer le premier.

Les opérations premier et défiler sont des opérations partielles, puisqu'elles ne peuvent pas être appliquées à une file vide.

Comme toujours, il est nécessaire d'avoir une opération d'initialisation : filevide et une pour vérifier si la structure contient des éléments : estvide.

Le type abstrait définissant les files est donc le suivant :

    types

        file

    utilise

        booléen, élément

    opérations

         filevide : → file
         enfiler : file x élément → file
         défiler : file → file
         premier : file → élément
         estvide : file → booléen

    préconditions

        défiler(f) est-défini-ssi estvide(f) = Faux
        premier(f) est-défini-ssi estvide(f) = Faux

    axiomes

        estvide(f) = Vrai ⇒ premier(enfiler(f,e)) = e
        estvide(f) = Faux ⇒ premier(enfiler(f,e)) = premier(f)
        estvide(f) = Vrai ⇒ défiler(enfiler(f,e)) = filevide
        estvide(f) = Faux ⇒ défiler(enfiler(f,e)) = enfiler(défiler(f),e)
        estvide(filevide) = Vrai
        estvide(enfiler(f,e)) = Faux

    avec

           file f
        élément e